#!/usr/bin/python
# -*- coding: utf-8 -*-

"""Project Euler Solution 027

Copyright (c) 2011 by Robert Vella - robert.r.h.vella@gmail.com

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
"""

import cProfile
from euler.numbers.primes import isprime, Primes
from euler.list_functions import max_by

def get_answer():
    """Question:
    
    Euler published the remarkable quadratic formula:

    n² + n + 41
    
    It turns out that the formula will produce 40 primes for the 
    consecutive values n = 0 to 39. However, when n = 40, 
    402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly 
    when n = 41, 41² + 41 + 41 is clearly divisible by 41.
    
    Using computers, the incredible formula  n² − 79n + 1601 was 
    discovered, which produces 80 primes for the consecutive values 
    n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.
    
    Considering quadratics of the form:
    
        n² + an + b, where |a| < 1000 and |b| < 1000
    
        where |n| is the modulus/absolute value of n
        e.g. |11| = 11 and |−4| = 4
    
    Find the product of the coefficients, a and b, for the quadratic 
    expression that produces the maximum number of primes for consecutive 
    values of n, starting with n = 0.
    """
    
    #Initialise cache for prime numbers
    primes = Primes()
    
    def evaluate_formula(a, b, n):
        """Returns the value for the quadratic formula n**2 + an + b."""
        
        return n ** 2 + a * n + b
    
    def get_number_of_primes(a, b):
        """Returns the number of times that the quadratic formula
        n^2 + an + b evaluates to a prime number for consecutive values of
        n.
        """
        
        n = 0
        
        while isprime(evaluate_formula(a, b, n), primes):
            n += 1
        
        return n + 1
    
    #Get the a, b pair for which the formula n**2 + an + b, gives the highest
    #number of primes for consecutive values of n.
    max_a_b = max_by(lambda a_b: get_number_of_primes(a_b["a"], a_b["b"]),
                     ({"a": a, "b": b} for a in xrange(-1000, 1001) 
                        for b in xrange(-1000, 1001))
                    )
    
    #Return result.
    return max_a_b["a"] * max_a_b["b"]    

if __name__ == "__main__":
    cProfile.run("print(get_answer())")
